import tool.TreeNode;

/**
 * 给定二叉树的根节点root，找出存在于 不同 节点A 和B之间的最大值 V，其中V = |A.val - B.val|，且A是B的祖先。
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 * <p>
 * 示例 1：
 * 输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 * 输出：7
 * 解释：
 * 我们有大量的节点与其祖先的差值，其中一些如下：
 * |8 - 3| = 5
 * |3 - 7| = 4
 * |8 - 1| = 7
 * |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 * <p>
 * 示例 2：
 * 输入：root = [1,null,2,null,0,3]
 * 输出：3
 * <p>
 * 提示：
 * 树中的节点数在2到5000之间。
 * 0 <= Node.val <= 105
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01026m {
    private int ans;

    public int maxAncestorDiff(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private int[] dfs(TreeNode root) {
        int[] lv = root.left != null ? dfs(root.left) : new int[]{root.val, root.val}; // 左子树的最小值和最大值，子树为空则取自身
        int[] rv = root.right != null ? dfs(root.right) : new int[]{root.val, root.val}; // 右子树的最小值和最大值，子树为空则取自身
        int min = Math.min(lv[0], rv[0]); // 取出左右子树的最小值
        int max = Math.max(lv[1], rv[1]); // 取出左右子树的最大值
        ans = Math.max(ans, Math.max(Math.abs(root.val - min), Math.abs(root.val - max))); // 计算结果
        return new int[]{Math.min(min, root.val), Math.max(max, root.val)}; // 返回与当前节点做比较后的最值
    }

    /*
    private int[] dfs(TreeNode root) {
        if (root == null) return null;
        int[] lv = dfs(root.left);
        int[] rv = dfs(root.right);
        if (lv == null && rv == null) {
            return new int[]{root.val, root.val};
        }
        if (lv != null && rv != null) {
            int min = Math.min(lv[0], rv[0]);
            int max = Math.max(lv[1], rv[1]);
            ans = Math.max(ans, Math.max(Math.abs(root.val - min), Math.abs(root.val - max)));
            return new int[]{Math.min(min, root.val), Math.max(max, root.val)};
        }
        if (lv != null) {
            ans = Math.max(ans, Math.max(Math.abs(root.val - lv[0]), Math.abs(root.val - lv[1])));
            return new int[]{Math.min(lv[0], root.val), Math.max(lv[1], root.val)};
        }
        ans = Math.max(ans, Math.max(Math.abs(root.val - rv[0]), Math.abs(root.val - rv[1])));
        return new int[]{Math.min(rv[0], root.val), Math.max(rv[1], root.val)};
    }*/
}
